<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>astar寻路算法</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="astar寻路算法">astar寻路算法</h1>
<h1 id="1-lc-675-cut-off-trees-for-golf-event">1. LC 675. Cut Off Trees for Golf Event</h1>
<p>本地需要某种寻路算法来找到 给定两点间的最短距离</p>
<h2 id="11-bfs">1.1 bfs</h2>
<pre><code class="language-python"><div>    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">bfs</span><span class="hljs-params">(self, forest, sx, sy, tx, ty, m, n)</span>:</span>
        
        <span class="hljs-comment">#queue = collections.deque([(sx, sy, 0)])</span>
        queue = [(sx, sy)]
        visited = {(sx, sy): <span class="hljs-number">1</span>}
        d = <span class="hljs-number">0</span>
        num = <span class="hljs-number">1</span>
        <span class="hljs-keyword">while</span> queue:
            sr, sc = queue.pop(<span class="hljs-number">0</span>)
            <span class="hljs-keyword">if</span> sr == tx <span class="hljs-keyword">and</span> sc == ty: <span class="hljs-keyword">return</span> d
            <span class="hljs-keyword">for</span> x, y <span class="hljs-keyword">in</span> [[<span class="hljs-number">1</span>, <span class="hljs-number">0</span>], [<span class="hljs-number">0</span>, <span class="hljs-number">1</span>], [<span class="hljs-number">-1</span>, <span class="hljs-number">0</span>], [<span class="hljs-number">0</span>, <span class="hljs-number">-1</span>]]:
                nr, nc = sr+x, sc+y
                <span class="hljs-keyword">if</span> <span class="hljs-number">0</span> &lt;= nr &lt; m <span class="hljs-keyword">and</span> <span class="hljs-number">0</span> &lt;= nc &lt; n <span class="hljs-keyword">and</span> (nr,nc) <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> visited <span class="hljs-keyword">and</span> forest[nr][nc]:
                    <span class="hljs-comment">#visited[nr][nc] = True</span>
                    visited[(nr, nc)] = <span class="hljs-number">1</span>
                    queue.append((nr, nc))
                    
            num -= <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> num == <span class="hljs-number">0</span>:
                num = len(queue)
                d += <span class="hljs-number">1</span>
                    
        
        <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
</div></code></pre>
<h2 id="12-astar">1.2 astar</h2>
<h3 id="astar-v1">astar v1</h3>
<p>提交后会超时, 关键是每次从open集合里面找最小的节点，效率太低。用的是遍历的办法。</p>
<pre><code class="language-python"><div>    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">astar</span><span class="hljs-params">(self, forest, sx, sy, tx, ty, m, n)</span>:</span>
        opend = []
        opend.append((sx,sy))
        closed = set()
        g = {(sx,sy): <span class="hljs-number">0</span>}
        h = {(sx,sy): abs(sx-tx)+abs(sy-ty)}
        <span class="hljs-keyword">while</span> opend:
            sr, sc = opend[<span class="hljs-number">-1</span>]
            <span class="hljs-keyword">for</span> ox,oy <span class="hljs-keyword">in</span> opend:  <span class="hljs-comment"># 就是这里效率低</span>
                <span class="hljs-keyword">if</span> g[(ox,oy)] + h[(ox,oy)] &lt; g[(sr,sc)] + h[(sr,sc)]:
                    sr, sc = ox, oy
            opend.remove((sr,sc))
            
            closed.add((sr,sc))
            <span class="hljs-keyword">if</span> sr==tx <span class="hljs-keyword">and</span> sc==ty:
                <span class="hljs-keyword">return</span> g[(sr,sc)] + h[(sr,sc)]
            
            <span class="hljs-keyword">for</span> x, y <span class="hljs-keyword">in</span> [[<span class="hljs-number">1</span>, <span class="hljs-number">0</span>], [<span class="hljs-number">0</span>, <span class="hljs-number">1</span>], [<span class="hljs-number">-1</span>, <span class="hljs-number">0</span>], [<span class="hljs-number">0</span>, <span class="hljs-number">-1</span>]]:
                nr, nc = sr+x, sc+y
                <span class="hljs-keyword">if</span> <span class="hljs-number">0</span> &lt;= nr &lt; m <span class="hljs-keyword">and</span> <span class="hljs-number">0</span> &lt;= nc &lt; n <span class="hljs-keyword">and</span> (nr,nc) <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> closed <span class="hljs-keyword">and</span> forest[nr][nc]: 
                    <span class="hljs-keyword">if</span> (nr,nc) <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> g:
                        g[(nr,nc)] = <span class="hljs-number">1</span> + g[(sr,sc)]
                        h[(nr,nc)] = abs(nr-tx) + abs(nc-ty)
                        opend.append((nr,nc))
                    <span class="hljs-keyword">else</span>:
                        <span class="hljs-keyword">if</span> g[(nr,nc)] &gt; <span class="hljs-number">1</span> + g[(sr,sc)]:
                            g[(nr,nc)] = <span class="hljs-number">1</span> + g[(sr,sc)]
        
        <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>       
    
</div></code></pre>
<h3 id="astar-v2">astar v2</h3>
<p>这里可以借用dijkstra 最小堆的处理办法。 可以将同一个节点重复压入最小堆，只要保证最小堆顶点是open集合最小的那个即可.</p>
<pre><code class="language-python"><div>    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">astar</span><span class="hljs-params">(self, forest, sx, sy, tx, ty, m, n)</span>:</span>
        opend = []
        closed = set()
        g = {(sx,sy): <span class="hljs-number">0</span>}
        h = {(sx,sy): abs(sx-tx)+abs(sy-ty)}
        t = g[(sx,sy)] + h[(sx,sy)]
        opend.append((t,sx,sy))
        <span class="hljs-keyword">while</span> opend:
            d, sr, sc = heapq.heappop(opend)
            closed.add((sr,sc))
            <span class="hljs-keyword">if</span> sr==tx <span class="hljs-keyword">and</span> sc==ty:
                <span class="hljs-keyword">return</span> d
            
            <span class="hljs-keyword">for</span> x, y <span class="hljs-keyword">in</span> [[<span class="hljs-number">1</span>, <span class="hljs-number">0</span>], [<span class="hljs-number">0</span>, <span class="hljs-number">1</span>], [<span class="hljs-number">-1</span>, <span class="hljs-number">0</span>], [<span class="hljs-number">0</span>, <span class="hljs-number">-1</span>]]:
                nr, nc = sr+x, sc+y
                <span class="hljs-keyword">if</span> <span class="hljs-number">0</span> &lt;= nr &lt; m <span class="hljs-keyword">and</span> <span class="hljs-number">0</span> &lt;= nc &lt; n <span class="hljs-keyword">and</span> (nr,nc) <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> closed <span class="hljs-keyword">and</span> forest[nr][nc]: 
                    <span class="hljs-keyword">if</span> (nr,nc) <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> g:
                        g[(nr,nc)] = <span class="hljs-number">1</span> + g[(sr,sc)]
                        h[(nr,nc)] = abs(nr-tx) + abs(nc-ty)
                        d = g[(nr,nc)] + h[(nr,nc)]
                        heapq.heappush(opend,(d, nr,nc))
                    <span class="hljs-keyword">else</span>:
                        <span class="hljs-keyword">if</span> g[(nr,nc)] &gt; <span class="hljs-number">1</span> + g[(sr,sc)]:
                            g[(nr,nc)] = <span class="hljs-number">1</span> + g[(sr,sc)]
                            d = g[(nr,nc)] + h[(nr,nc)]
                            heapq.heappush(opend,(d, nr,nc))
        
        <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>     
</div></code></pre>
<h3 id="v3">v3</h3>
<p>官方答案比我的版本简洁了很多</p>
<ul>
<li><a href="https://leetcode.com/problems/cut-off-trees-for-golf-event/solution/">https://leetcode.com/problems/cut-off-trees-for-golf-event/solution/</a></li>
</ul>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">astar</span><span class="hljs-params">(forest, sr, sc, tr, tc)</span>:</span>
    R, C = len(forest), len(forest[<span class="hljs-number">0</span>])
    heap = [(<span class="hljs-number">0</span>, <span class="hljs-number">0</span>, sr, sc)]
    cost = {(sr, sc): <span class="hljs-number">0</span>}
    <span class="hljs-keyword">while</span> heap:
        f, g, r, c = heapq.heappop(heap)
        <span class="hljs-keyword">if</span> r == tr <span class="hljs-keyword">and</span> c == tc: <span class="hljs-keyword">return</span> g
        <span class="hljs-keyword">for</span> nr, nc <span class="hljs-keyword">in</span> ((r<span class="hljs-number">-1</span>,c), (r+<span class="hljs-number">1</span>,c), (r,c<span class="hljs-number">-1</span>), (r,c+<span class="hljs-number">1</span>)):
            <span class="hljs-keyword">if</span> <span class="hljs-number">0</span> &lt;= nr &lt; R <span class="hljs-keyword">and</span> <span class="hljs-number">0</span> &lt;= nc &lt; C <span class="hljs-keyword">and</span> forest[nr][nc]:
                ncost = g + <span class="hljs-number">1</span> + abs(nr - tr) + abs(nc - tc)
                <span class="hljs-keyword">if</span> ncost &lt; cost.get((nr, nc), <span class="hljs-number">9999</span>):
                    cost[nr, nc] = ncost
                    heapq.heappush(heap, (ncost, g+<span class="hljs-number">1</span>, nr, nc))
    <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
</div></code></pre>
<h1 id="13-hadlocks-algorithm">1.3 Hadlock's Algorithm</h1>
<ul>
<li><a href="https://leetcode.com/problems/cut-off-trees-for-golf-event/solution/">https://leetcode.com/problems/cut-off-trees-for-golf-event/solution/</a></li>
</ul>
<p>看不太懂</p>
<p>Approach #3: Hadlock's Algorithm [Accepted]</p>
<h4 id="intuition">Intuition</h4>
<p>Without any obstacles, the distance from source = (sr, sc) to target = (tr, tc) is simply taxi(source, target) = abs(sr-tr) + abs(sc-tc). This represents a sort of minimum distance that must be travelled. Whenever we walk &quot;away&quot; from the target, we increase this minimum by 2, as we stepped 1 move, plus the taxicab distance from our new location has increased by one.</p>
<p>Let's call such a move that walks away from the target a detour. It can be proven that the distance from source to target is simply taxi(source, target) + 2 * detours, where detours is the smallest number of detours in any path from source to target.</p>
<h4 id="algorithm">Algorithm</h4>
<p>With respect to a source and target, call the detour number of a square to be the lowest number of detours possible in any path from source to that square. (Here, detours are defined with respect to target - the number of away steps from that target.)</p>
<p>We will perform a priority-first-search in order of detour number. If the target is found, it was found with the lowest detour number and therefore the lowest corresponding distance. This motivates using processed, keeping track of when nodes are expanded, not visited - nodes could potentially be visited twice.</p>
<p>As each neighboring node can only have the same detour number or a detour number one higher, we will only consider at most 2 priority classes at a time. Thus, we can use a deque (double ended queue) to perform this implementation. We will place nodes with the same detour number to be expanded first, and nodes with a detour number one higher to be expanded after all nodes with the current number are done.</p>
<pre><code class="language-Python"><div>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">hadlocks</span><span class="hljs-params">(forest, sr, sc, tr, tc)</span>:</span>
    R, C = len(forest), len(forest[<span class="hljs-number">0</span>])
    processed = set()
    deque = collections.deque([(<span class="hljs-number">0</span>, sr, sc)])
    <span class="hljs-keyword">while</span> deque:
        detours, r, c = deque.popleft()
        <span class="hljs-keyword">if</span> (r, c) <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> processed:
            processed.add((r, c))
            <span class="hljs-keyword">if</span> r == tr <span class="hljs-keyword">and</span> c == tc:
                <span class="hljs-keyword">return</span> abs(sr-tr) + abs(sc-tc) + <span class="hljs-number">2</span>*detours
            <span class="hljs-keyword">for</span> nr, nc, closer <span class="hljs-keyword">in</span> ((r<span class="hljs-number">-1</span>, c, r &gt; tr), (r+<span class="hljs-number">1</span>, c, r &lt; tr),
                                   (r, c<span class="hljs-number">-1</span>, c &gt; tc), (r, c+<span class="hljs-number">1</span>, c &lt; tc)):
                <span class="hljs-keyword">if</span> <span class="hljs-number">0</span> &lt;= nr &lt; R <span class="hljs-keyword">and</span> <span class="hljs-number">0</span> &lt;= nc &lt; C <span class="hljs-keyword">and</span> forest[nr][nc]:
                    <span class="hljs-keyword">if</span> closer:
                        deque.appendleft((detours, nr, nc))
                    <span class="hljs-keyword">else</span>:
                        deque.append((detours+<span class="hljs-number">1</span>, nr, nc))
    <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
</div></code></pre>

    </body>
    </html>